Предлагается новый подход к определению ациклических алгебраических байесовских сетей (ААБС). Они определяются как дерево смежности с идеалами цепочек конъюнкций в узлах, при этом на идеалах заданы точечные или интервальные оценки вероятности истинности. На языке матриц изложены требования непротиворечивости к заданию вероятностного распределения на идеале цепочек конъюнкций; затем на основе нового определения рассматриваются вероятностная семантика и свойства ААБС.
В работе рассмотрена проблема преобразования первичной структуры алгебраической байесовской сети с интервальными оценками вероятности к первичной структуре такой сети, стохастически эквивалентной исходной в задаче преобразования первичной структуры такой сети к ацикличной. Показано, что такое преобразование допустимо лишь в том случае, когда гиперграф, соответствующий результирующий первичной структуре, пореберно содержит гиперграф, соответствующий исходной первичной структуре. Предложен способ построения вероятностных оценок результирующей первичной структуры, делающий ее стохастически эквивалентной исходной.
Предложена двухэтапная схема синтеза подмножеств минимальных графов смежности, предполагающая построение трех множеств (стереосепараторов, их владений и обязательных ребер) по множеству подалфавитов и построение по этим четырем множествам множеств жил определенного вида для каждого стереосепаратора. Систематизированы алгоритмы, реализующие оба этапа, и дана оценка их сложности.
Одним из условий эффективности алгоритмов логико-вероятностного вывода в алгебраической байесовской сети (АБС) является условие ацикличности представляющего её графа. Введение гиперграфового представления структур АБС позволило применять методы преобразования данного графа к ациклическому виду, основывающиеся на методах теории древовидной декомпозиции. Рассмотрена общая схема метода приведения сети к ациклическому виду, использующего элименирующие последовательности. Приведены основные классы эвристических алгоритмов поиска элименирующих последовательностей, применимых в контексте преобразования АБС, а так же оценки их сложности и качества получаемых результатов.
В статье рассматриваются ключевые элементы програмной реализации фрагмента знаний алгебраической байесовской сети на языке С++. Фрагмент знаний реализован в виде отдельного класса, обеспечивающего хранение оценок истинности и имеющего ряд методов реализующих алгоритмы обработки фрагмента знаний, таких как поддержания непротиворечивости и апостериорный вывод.
Второй задачей апостериорного вывода является пересчет имеющихся оценок вероятности истинности при условии поступившего свидетельства. Цель статьи в анализе нелинейной задачи оптимизации, возникающей при пропагации атомарного стохастического свидетельства во фрагменте знаний с интервальными оценками алгебраической байесовской сети. Переход к накрывающим оценкам границ интервала позволяет привести задачу нелинейной оптимизации к серии задач квадратичного или дробно-линейного программирования.
В статье рассматривается локальный апостериорный вывод в алгебраических байесовских сетях. Для трёх видов свидетельств (детерминированного, стохастического и неточного) описывается способ проведения вывода и доказываются оценки сложности предлагаемых вычислений. В случае, когда вывод сводится к решению задач линейного программирования, оценка сложности даётся в виде числа таких задач, а также оценки числа переменных и ограничений в них. В остальных случаях сложность описывается в числе арифметических операций.
Рассматриваются вопросы проверки и поддержания непротиворечивости алгебраических байесовских сетей. Даются формальные описания алгоритмов, доказывается их корректность и приводятся оценки вычислительной сложности.
Предлагается алгоритм формирования вторичной структуры алгебраической байесовской сети (АБС) на основе ее первичной структуры. Вторичная структура АБС представляет собой граф смежности с минимальным числом ребер. Приведено доказательство корректности работы алгоритма.
1 - 9 из 9 результатов